The present invention is generally directed to the storage, manipulation and retrieval of information from a memory. More particularly, the present invention is directed to a method and apparatus for locating the longest prefix match in a content addressable memory.
Content addressable memory (CAM) is a known type of associative memory which provides for retrieval of information based on partial knowledge of that information. An exemplary CAM controller is disclosed in pending U.S. application Ser. No. 08/970,718 filed Nov. 14, 1997, now U.S. Pat. No. 6,226,710 B1, entitled xe2x80x9cContent Addressable Memory (CAM) Engine,xe2x80x9d referred to herein as the CAM-Engine, which is herein incorporated by reference in its entirety. In routing processors on networks, an important task is to determine a next destination address for a particular message. This task may be performed by using look up tables to match addresses to locations. If a match is found, the associated data is returned to the processor. Such lookup tables can be fairly large and thus a search using normal methods of storing data in a random access memory are time consuming. Usual methods are inefficient and unresponsive when managing large look up tables. Thus, there is a need in the art for improved methods for accessing information in content addressable memory.
An exemplary embodiment of the invention is a method and apparatus for determining the longest prefix match in a content addressable memory. A content addressable memory device comprises an application specific integrated circuit which interfaces between a general microprocessor and a random access memory so as to create an associative memory structure which includes transition nodes, significant nodes and arcs. A table including multiple data structures is created in the random access memory by the device for storing prefixes and associated data in a predetermined manner. The table is manipulated by the device in response to commands such as add data, delete data, and search for data by the microprocessor.
The above-discussed and other features and advantages of the present invention will be appreciated and understood by those skilled in the art from the following detailed description and drawings.